package sysu.el.graph.undi.algor;

import java.util.ArrayList;

import sysu.el.array.BoolArray;
import sysu.el.array.ints.ArrInt;
import sysu.el.graph.undi.UndiGT;

public class ChainSearcher {
	public UndiGT graph;
	public BoolArray chainTag; // Just for the chain memeber
	public ArrInt chain;
	public ArrayList<int[]> chains;
	public ArrayList<int[]> rings;
	
	public ChainSearcher(UndiGT g){
		graph = g;
		chainTag = new BoolArray(g.getNodeNum());
		chain = new ArrInt(g.getNodeNum() + 1);
		chains = new ArrayList<int[]>();
		rings = new ArrayList<int[]>();
	}
	
	public void startSearching(int node){
		int len = graph.getDegree(node);
		chainTag.setVisited(node);
		for (int i=0; i<len; i++){
			chain.reset();
			chain.add(node);
//			int cur = graph.adjNodes[node][i];
			int cur = graph.getList(node)[i];
			int pre = node;
			if (chainTag.isVisited(cur)) continue;
			while (graph.getDegree(cur) == 2){
				chain.add(cur);
				chainTag.setVisited(cur);
				int next = graph.adjNodes.getList(cur)[0];
				if (pre == next){
					next = graph.adjNodes.getList(cur)[1];
				}
				pre = cur;
				cur = next;
				if (cur == node){
					assert(chainTag.isVisited(cur = next));
					break;
				}
			}
			
			if (cur == node){
				chain.add(node);
				this.rings.add(chain.toArray());
			}
			else if (chain.counter > 2){
				chain.add(cur);
				this.chains.add(chain.toArray());
			}
		}
	}
	
	public void searchChaines(){
		chainTag.reset();
		for (int i=0; i<graph.getNodeNum(); i++){
			if (chainTag.isVisited(i)) continue;
			if (graph.getDegree(i) == 2) continue;
			this.startSearching(i);
		}
		
		for (int i=0; i<graph.getNodeNum(); i++){
			if (chainTag.isVisited(i)) continue;
			this.startSearching(i);
		} 
	}

}
